package com.wtgroup.demo.面试题;

/**
 * 无序数组中, 相邻数不相等, 找局部最小, 任意一个返回. 局部最小: 至少比相邻两边小, 首尾比傍边的一个小就可以.
 *
 * 暴力解法, 挨个看, 和前后对比, O(n). 二分法: 此处二分法特点在, 选中的一侧必有目标解, 但排除的一侧不一定就没有.
 * 我们只关心肯定有的一侧就可以了. 而"有序数组二分查找"排除的一侧比没有有效解.
 * 1) 0处上扬或N处下降, 直接返回. 2) 不在两端, 必在中间. 二分. a)直接是. b)必在其中一侧.
 * @author dafei
 * @version 0.1
 * @date 2021/4/5 11:29
 */
public class Q004_无序数组局部最小_S1 {

    public static void main(String[] args) {
        int[][] inputs = {
                {1,2,3},
                {3,1},
                {10,-1,8,0,-90},
                {10,-1,8,0,90},
                {-7},
                {64,-164,75,68,5,47,45,74} // 4
        };

        for (int[] input : inputs) {
            int r = m(input);
            int r2 = Q004_无序数组局部最小_S2.m(input, 0, input.length - 1);
            System.out.println(r + "--" + r2);
        }
    }

    private static int m(int[] input) {
        // 在外面提前搞定两端
        int n = input.length;
        if (n ==0) {
            return -1;
        }
        if (n ==1 || input[0] < input[1]) {
            return 0;
        }
        if (input[n -1] < input[n -2]) {
            return n-1;
        }

        int r = m0(input, 0, n - 1);
        return r;
    }

    public static int m0(int[] arr, int left, int right) {
        if (right-left<2) {
            return arr[left]<arr[right] ? left : right;
        }

        // 递归进来的, 两端已经搞定了: 左下降, 右上扬
        int mid = left + ((right-left)>>1);
        if (arr[mid-1] > arr[mid] && arr[mid+1] > arr[mid]) {
            return mid;
        }

        int ansIdx = 0;
        if (arr[mid] > arr[mid-1]) {
            // 左侧肯定有, 右侧就不管了
            ansIdx = m0(arr, left, mid);
        } else {
            // arr[mid] > arr[mid+1] 必成立, 右侧肯定有
            ansIdx = m0(arr, mid, right); // mid 需要继续包含进去
        }

        return ansIdx;
    }
}
